The present invention relates to decoding techniques used in data communications.
In a data communications system in which convolutional coding is used, a data receiver typically applies a "maximum likelihood decoding" procedure to a sequence of received signal points in order to estimate the sequence of symbols sent by a data transmitter. Generally, in a convolutional code, the symbol that is output by a data transmitter at a particular point in time is dependent on the state of the code. In other words, a convolutional code can be modeled as a state machine, with each transition between states being associated with the transmission of a particular symbol and the current state being dependent on the previous states of the convolutional code. As a result, any sequence of transmitted symbols, which can also be referred to as a "path," is representative of a particular sequence of state transitions in the convolutional code. Maximum likelihood decoding in the data receiver essentially selects that sequence of symbols that have the largest probability of having been transmitted given the particular received sequence of signal points. Theoretically, the maximum likelihood decoder compares the received signal point sequence to all possible transmitted symbol sequences, or paths, and then makes an estimate as to which sequence of symbols, or path, was transmitted. This type of operation causes the complexity of the maximum likelihood decoder to increase exponentially with the number of possible paths. However, as is known in the art, the complexity of the maximum likelihood decoder is reduced by the use of the "Viterbi algorithm," which has a complexity that only increases at a linear rate.
In the Viterbi algorithm a "branch metric," or a "transition metric," is calculated for each received signal point. The branch metric, or transition metric is essentially a measure of the possible error in the received signal. In a very general sense, the received signal point is compared to all the possible symbols that could have been received at that point in the receiver. However, the Viterbi algorithm does not compare each received signal point sequence to all possible transmitted symbol sequences or paths. The advantage of the Viterbi algorithm is that for each state of the convolutional code only the path that has the smallest cumulative value for the branch metric is retained by the decoder in considering the possible paths for any subsequent received signal points.
Notwithstanding the advantages of the Viterbi algorithm, unfortunately, if the number of states in the convolutional code is large, then the number of branch metric computations that must be made for each received signal point is also large. Moreover, as the data rate increases, the time available to perform the branch metric computation decreases. Consequently, at higher data rates, faster and typically more costly processing circuitry must be used to perform the required multiplications and additions for high-speed decoding.
Before proceeding with a description of an illustrative embodiment, it should be noted that the various digital signaling concepts described herein--with the exception, of course, of the inventive concept itself--are all well known in, for example, the digital radio and voiceband data transmission (modem) arts and thus are not described in detail herein. These include such concepts as multidimensional signaling using 2N-dimensional channel symbol constellations, where N is some integer; trellis coding; fractional coding; scrambling; passband shaping; equalization; etc.